import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(findSubstring("barfoothefoobarman", new String[]{"foo", "bar"}));
        System.out.println(findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "word"}));
        System.out.println(findSubstring("barfoofoobarthefoobarman", new String[]{"bar", "foo", "the"}));
        System.out.println(findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"}));
        System.out.println(findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "word"}));
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        Node root = new Node(new HashMap<>());

        for (String w : words) {
            root.put(w.toCharArray());
        }


        List<Integer> result = new ArrayList<>();
        char[] content = s.toCharArray();
        int size = words[0].length();
        int total = words[0].length() * words.length;
        FOR:
        for (int i = 0; i < content.length; i++) {
            if (i + total > content.length) {
                break;
            }
            root.flashCount();

            int left = words.length;
            int start = i;
            int end = start + size;
            while (left > 0) {
                if (!root.find(Arrays.copyOfRange(content, start, end))){
                    continue FOR;
                }

                left--;
                start = end;
                end = start + size;
            }

            result.add(i);

        }
        return result;
    }

    private static int sum(int i) {
        if (i == 1) {
            return i;
        }

        int num = i / 2;
        if ((i & 1) == 1) {
            return (1 + i) * num + num + 1;
        } else {
            return (1 + i) * num;
        }
    }

    private static class Node {
        private int num = -1;
        private int count = 0;
        private final Map<Character, Node> sonMap;

        Node(Map<Character, Node> m) {
            sonMap = m;
        }

        Node(int num) {
            sonMap = null;
            this.num = num;
        }

        private void put(char... charArr) {
            char c = charArr[0];
            if (charArr.length == 1) {
                if (!sonMap.containsKey(c)) {
                    Node n = new Node(1);
                    sonMap.put(c, n);
                } else {
                    sonMap.get(c).num++;
                }
            } else {
                if (sonMap.containsKey(c)) {
                    sonMap.get(c).put(Arrays.copyOfRange(charArr, 1, charArr.length));
                } else {
                    Node n = new Node(new HashMap<>());
                    sonMap.put(c, n);
                    n.put(Arrays.copyOfRange(charArr, 1, charArr.length));
                }
            }
        }

        private boolean find(char... charArr) {
            char c = charArr[0];
            if (charArr.length == 1) {
                if (sonMap.containsKey(c)) {
                    Node leaf = sonMap.get(c);
                    leaf.count++;
                    return leaf.count <= leaf.num;
                } else {
                    return false;
                }
            } else {
                if (sonMap.containsKey(c)) {
                    return sonMap.get(c).find(Arrays.copyOfRange(charArr, 1, charArr.length));
                } else {
                    return false;
                }
            }
        }

        private void flashCount() {
            if (Objects.isNull(sonMap)) {
                this.count =0;
                return;
            }
            for (Map.Entry<Character, Node> entry : sonMap.entrySet()) {
                entry.getValue().flashCount();
            }
        }

    }


}